package com.example.base

import java.util.*

/**
 * Author: liaohailong
 * Date: 2021/11/23
 * Time: 20:21
 * Description:
 **/
class BinaryStudy {

    /**
     * 二分法 - 插入value，如果arr中已存在value，则不重复插入
     * @param arr 有序集合
     * @param value 插入目标值
     */
    fun binaryInsert(arr: ArrayList<Long>, value: Long) {
        // 第一次插入
        if (arr.isEmpty()) {
            arr.add(value)
            return
        }

        val count = arr.size
        var low = 0
        var high = count
        while (true) {
            val mid = low + (high - low) / 2
            // 集合中存在，不用插入
            if (arr[mid] == value) return

            if (arr[mid] < value) {
                low = mid + 1
            } else if (arr[mid] > value) {
                high = mid - 1
            }

            if (high - low <= 1) break // 范围缩小到了1个单位，可以直接判断了
        }

        // 可能插入值大于集合内所有值，low和high一直往右靠，越界保护一下
        low = Math.min(count - 1, low)
        high = Math.min(count - 1, high)
        if (value < arr[low]) {
            // 比左边界还小，插入到low前面
            arr.add(low, value)
        } else if (value > arr[high]) {
            // 比有边界还大，插入到high后面
            arr.add(index = high + 1, value)
        }
    }

    /**
     * 二分法 - 查找离value最近的值
     * @param arr 有序集合
     * @param value 查找目标值
     * @param max 当不到时，最大误差，超过等于没找到
     * @return 找到的的话，范围arr中的下标，找不到的话返回-1
     */
    fun binaryCloseSearch(arr: ArrayList<Long>, value: Long, max: Long): Int {
        if (arr.isEmpty()) return -1

        val count = arr.size
        var low = 0
        var high = arr.size
        while (true) {
            val mid = low + (high - low) / 2

            // 找到了
            if (arr[mid] == value) return mid

            if (arr[mid] < value) {
                low = mid + 1
            } else if (arr[mid] > value) {
                high = mid - 1
            }

            if (high - low <= 1) break // 范围缩小到了1个单位，可以直接判断了
        }

        // 可能插入值大于集合内所有值，low和high一直往右靠，越界保护一下
        low = Math.min(count - 1, low)
        high = Math.min(count - 1, high)
        if (value <= arr[low]) {
            // 找到左边界，判断误差
            return if (arr[low] - value <= max) low else -1
        } else if (value >= arr[high]) {
            // 找到右边界，判断误差
            return if (value - arr[high] <= max) high else -1
        }
        return -1
    }
}